/**
 * @file:stack.hpp 
 * Implementation of stack
 */
/**
 * Copyright 2013 MIPT-COMPILER team
 */
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <sstream>
using namespace std;
    
template <class SType> 
class Stack 
{
public:
    struct StackList 
    {
        struct StackList *next;
        SType data;
    };
    StackList *edge;
    SType pop();
    Stack() 
    { 
        size = 0; 
    } 
    void push( SType x ); 
    inline bool empty()
    {
        if ( !size ) 
        {
            return true;
        }
        return false;
    }
    inline int length() 
    { 
        return size; 
    }
    ostream &operator << ( Stack<SType> object );
private:
    int size; // size - current length of Stack
};

class ExceptionEmpty { };

template <class SType>
ostream &operator << ( ostream &stream, Stack<SType> object ) 
{
    Stack<SType> buf;
    buf.edge = object.edge;
    int n = object.length(); 
    if ( n == 0 ) 
    {
        stream << "Stack is empty. \n";
        return stream;
    }
    for ( int i = 0; i < n; i++ )
    {
        stream << buf.edge->data << " ";
        buf.edge = buf.edge->next;
    } 
    stream << "\n"; 
    return stream;
} 

template <class SType> 
void Stack<SType>::push( SType new_item )
{
    StackList *new_list_element = new StackList;
    new_list_element->data = new_item;
    new_list_element->next = NULL;
    if ( size > 0 )
    {
        new_list_element->next = edge;
        edge = new_list_element;
    }
    else 
    {
        edge = new_list_element;
    }
    size++;
}

template <class SType> 
SType Stack<SType>::pop()
{
    if ( size < 1 )
        throw ExceptionEmpty();
    StackList *pop_element = edge;
    SType buf = edge->data;
    edge = edge->next; //if 'edge' is the last element, it will be just NULL
    size--;
    delete pop_element; 
    return buf;
}
